416. Partition Equal Subset Sum - LeetCode Solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        dp = [-1] * (len(nums)+ 1)
        
        avg = sum(nums) // 2
        @cache
        def trav(sum1, sum2, ptr):
            if ptr == len(nums):
                return sum1 == sum2
            
            if sum1> avg:
                return False
            if sum2 > avg:
                return False
            
            
            
            return trav(sum1+nums[ptr], sum2, ptr+1) or trav(sum1, sum2+nums[ptr], ptr+1)
            return dp[ptr]
        return trav(0, 0 , 0)